#include "main/utils.h"
#include "lib/list.h"
using namespace std;

ListNode* reverseList(ListNode* head) {
  ListNode* pre_node = nullptr;
  ListNode* cur_node = head;
  ListNode* tail_node = head;
  while (cur_node) {
    ListNode* next_node = cur_node->next;
    if (!next_node) {
      tail_node = cur_node;
    }
    cur_node->next = pre_node;
    pre_node = cur_node;
    cur_node = next_node;
  }
  return tail_node;
}

ListNode* findInterNode(ListNode* head) {
  auto fast_node = head;
  auto slow_node = head;
  while (fast_node) {
    fast_node = fast_node->next;
    if (fast_node) {
      fast_node = fast_node->next;
    }
    if (fast_node && slow_node) {
      slow_node = slow_node->next;
    }
  }
  auto ret = slow_node->next;
  slow_node->next = nullptr;
  return ret;
}

ListNode* reSort(ListNode* head) {
  auto inter_node = findInterNode(head);
  auto reverse_head = reverseList(inter_node);

  auto ret = head;
  while (head && reverse_head) {
    auto head_next = head->next;
    auto reverse_next = reverse_head->next;
    head->next = reverse_head;
    head = head->next;
    head->next = head_next;
    head = head->next;
    reverse_head = reverse_next;
  }
  return ret;
}

int main() {
  vector<int> vec = {1, 2, 3, 4, 5, 6, 7};
  ListNode* head = CreateList(vec);
  ListNode* ret = reSort(head);
  PrintList(ret);

  return 0;
}
